在CTF的加解密单元中，RSA是常见的加解密算法。在正确的配置RSA算法的情况下，目前来说还是无法破解的。但也有一些不黄金城官网配置或者不黄金城官网使用RSA算法的情况，在这些情况下，即使是使用了RSA算法，被加密的内容仍然有可能被破解。在CTF竞赛中，常常会将这种情况作为题目，从而使大家对RSA算法有更深的理解。以下是CTF比赛中常见的RSA算法题型。
01 低加密指数攻击
1.1 明文较小时适用情况一般针对e特别小的情况下，如e等于3。且n远大于c。这样c有可能等于明文的e次方。可通过对c进行开方获取明文题目说明#n: 0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793L#e: 0x3#c:0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365so,how to get the message? 题解
如上图题目，len（c）=228,len(n)=512,n远大于c，且e=3较�。虼丝梢猿⑹越锌浇饷�。
from gmpy2 import iroot
import libnum
e = 0x3
n =0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793
c =0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365
def smallEattack(c, e, n):
for i in range(10 ** 10):
res = iroot(n * i + c, e)
if res`1`:
print(libnum.n2s(int(res`0`)))
break
smallEattack(c,e,n)
1.2 hastad广播攻击
适用情况
使用相同的加密指数e加密相同的信息，发送给多于e个不同的人，可能收到低加密指数广播攻击，最终具有超过e个的密文。即n,c不同，m,e相同。一般会是e=k，然后给k组数据。
题目说明
题目来源：XCTF 4th-WHCTF-2017
题目描述：有一个年轻人得到了一份密文，身为老司机的你能帮他看看嘛？
题目附件：
`{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042,"e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461,"e": 10, "n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983,"e": 10, "n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052,"e": 10, "n":23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672,"e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087,"e": 10, "n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639,"e": 10, "n":25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352,"e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c":8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797,"e": 10, "n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247,"e": 10, "n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}`
题解
import gmpy2
import libnum
def crt(b,m):
'''中国剩余定理'''
#判断是否互素
for i in range(len(m)):
for j in range(i+1,len(m)):
if gmpy2.gcd(m`i`,m`j`) != 1:
print("m中含有不是互余的数")
return -1
#乘积
M= 1
for i in range(len(m)):
M *= m`i`
#求M/mi
Mm = ``
for i in range(len(m)):
Mm.append(M // m`i`)
#求Mm`i`的乘法逆元
Mm_ = ``
for i in range(len(m)):
_,a,_ = gmpy2.gcdext(Mm`i`,m`i`)
Mm_.append(int(a % m`i`))
#求MiM'ibi的累加
y= 0
for i in range(len(m)):
print(Mm`i` * Mm_`i` * b`i`)
y += (Mm`i` * Mm_`i` * b`i`)
y= y % M
return y
enc = `{"c":7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042,"e": 10,
"n":25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c":21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461,"e": 10,
"n":23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c":6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983,"e": 10,
"n":18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c":4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052,"e": 10,
"n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c":22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672,"e": 10,
"n":31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087,"e": 10,
"n":22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c":1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639,"e": 10,
"n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c":15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352,"e": 10,
"n":32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797,"e": 10,
"n":52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c":13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247,"e": 10,
"n":30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}`
e = 10
c = ``
n = ``
for i in range(len(enc)):
c.append(enc`i``"c"`)
n.append(enc`i``"n"`)
r = crt(c,n)
res = gmpy2.iroot(r,e)
if(res`1` == True):
print(libnum.n2s(int(res`0`))) #转为字符串
1.3 CopperSmith部分信息攻击-明文高位泄漏
适用情况
给出了明文的高位数据，求所有明文数据
题目说明
('n=', '0xf85539597ee444f3fcad07142ecf6eaae5320301244a7cedc50b2beed7e60ffa11ccf28c1a590fb81346fb16b0cecd046a1f63f0bf93185c109b8c93068ec02fL')
('e=', '0x3')
('c=','0xa75c3c8a19ed9c911d851917e442a8e7b425e4b7f92205ca532a2ab0f5abe6cb86d164cc61374877f9e88e7bca606b43c79f1d59deadfcc68c3db52e5fc42f0L')
('m=','0x666c6167206973203a746573743132313131313131313131313133343536000000000000000000')
题解
在线网站（https://sagecell.sagemath.org/）上执行
e = 0x3
b=0x666c6167206973203a746573743132313131313131313131313133343536000000000000000000
n =0xf85539597ee444f3fcad07142ecf6eaae5320301244a7cedc50b2beed7e60ffa11ccf28c1a590fb81346fb16b0cecd046a1f63f0bf93185c109b8c93068ec02f
c=0xa75c3c8a19ed9c911d851917e442a8e7b425e4b7f92205ca532a2ab0f5abe6cb86d164cc61374877f9e88e7bca606b43c79f1d59deadfcc68c3db52e5fc42f0
kbits=72
PR. = PolynomialRing(Zmod(n))
f = (x + b)^e-c
x0 = f.small_roots(X=2^kbits, beta=1)`0`
print("x: %s" %hex(int(x0)))
1.4 CopperSmith部分信息攻击-因子高位泄漏
适用情况
给出了p，或者q的部分高位，求完整p/q
题目说明
('n=','0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abddL')
('p=','0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000L')
('e=', '0x3')
('c=','0x428a95e5712e8aa22f6d4c39ee5ec85f422608c2f141abf22799c1860a5e343068ab55dfb5c99a7085714f4ce8950e85d8ed0a11fce3516cf66a641dca8321eeL')
题解
在线网站（https://sagecell.sagemath.org/）上执行
p = 0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000
n =0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abdd
kbits = 60
PR. = PolynomialRing(Zmod(n))
f = x + p
x0 = f.small_roots(X=2^kbits, beta=0.4)`0`
print("x: %s" %hex(int(x0)))
p = p+x0
print("p: ", hex(int(p)))
assert n % p == 0
q = n/int(p)
print("q: ", hex(int(q)))
02 低解密指数攻击
适用情况
当解密指数d过小时，则可能为低解密指数攻击。反过来，就是e会是比较大。
题目说明
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e =11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
题解
# -*- coding: cp936 -*-
import gmpy2
import time
# 展开为连分数
def continuedFra(x, y):
cF = ``
while y:
cF += `x / y`
x, y = y, x % y
return cF
def Simplify(ctnf):
numerator = 0
denominator = 1
for x in ctnf`::-1`:
numerator, denominator = denominator, x * denominator + numerato
return (numerator, denominator)
# 连分数化简
def calculateFrac(x, y):
cF = continuedFra(x, y)
cF = map(Simplify, (cF`0:i` for i in xrange(1, len(cF))))
return cF
# 解韦达定理
def solve_pq(a, b, c):
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) / (2 * a), (-b - par) / (2 * a)
def wienerAttack(e, n):
for (d, k) in calculateFrac(e, n):
if k == 0: continue
if (e * d - 1) % k != 0: continue
phi = (e * d - 1) / k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return abs(int(p)), abs(int(q))
print 'not find!'
time.clock()
n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827
e =11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517
c = 9472193174575536616954091686751964873836697237500198884451530469300324470671555310791335185133679697207007374620225900775502162690848135615431624557389304657410880981454777737587420426091879654002644281066474715074536611611252677882396384453641127487515845176069574754606670518031472235144795376526854484442135299818868525539923568705203042265537204111153151119105287648912908771710419648445826883069030285651763726003413418764301988228077415599665616637501056116290476861280240577145515875430665394216054222788697052979429015400411487342877096677666406389711074591330476335174211990429870900468249946600544116793793
p, q = wienerAttack(e, n)
print '`+`Found!'
print ' `-`p =',p
print ' `-`q =',q
print ' `-`n =',p*q
d = gmpy2.invert(e,(p-1)*(q-1))
print ' `-`d =', d
print ' `-`m is:' + '{:x}'.format(pow(c,d,n)).decode('hex')
print '
`!`Timer:', round(time.clock(),2),'s'
print '`!`All Done!'
03 共模攻击
适用情况对同一明文m多次使用相同n，不同e加密，得到不同密文c。也就是n相同，e不同，所以c不同。题目说明n =158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043e = `665213, 368273`c = `16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425L,59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436L`求 m题解# -*- coding: cp936 -*-import timeimport gmpy2n =158052722013789461456896900244510199169216575693048895162538548356466884311543740968048825149608833390255268602486435690724338965409521812963337715301197225841194835534751041470231293288252951274190599189716955573428884560130364021535005115652592074445852835422027406556727605302404510264249211145063332337043e = `665213, 368273`c = `16698617641888248664694980135332125531792692516788088682722832061393117609508765284473236240256421599515450690670639565968165473479697383505401285976148490839526672808730165847471005704945978274496508928460578173068717106075169723401049489389383596761956301440156581021583368058047939083755488885694261340425L,59192887933967939708054321952273893559113509451228797382728687616356609407020086787061368452871936378934964292805289941535766263083244529814852043063188312786173717046316177403357053871483983775362121186037776932260378728059531236711960979620603784044468207000654149190295060179235411429700710154759043236436L`print '`+`Detecting m...'time.clock()c1 = c`0`c2 = c`1`e1 = e`0`e2 = e`1`s = gmpy2.gcdext(e1, e2)s1 = s`1`s2 = s`2`# 求模反元素if s1 < 0: s1 = -s1 c1 = gmpy2.invert(c1, n)elif s2 < 0: s2 = -s2 c2 = gmpy2.invert(c2, n)m = pow(c1, s1, n) * pow(c2, s2, n) % nprint ' `-`m is:' + '{:x}'.format(int(m)).decode('hex')print '
`!`Timer:', round(time.clock(),2),'s'print '`!`All Done!'参考链接CTF中RSA的常见攻击方法：https://www.tr0y.wang/2017/11/06/CTFRSA/CTF中常见的RSA相关问题总结：https://xz.aliyun.com/t/2446#toc-5CTF-RSA总结：https://forum.butian.net/share/478CTF中的RSA基本套路：https://blog.ycdxsb.cn/62ad53e2.html
浙公网安备 33010502006954号
浙ICP备12021012号-1
